// 力扣20.有效的括号: https://leetcode.cn/problems/valid-parentheses/
// 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效
package main

import (
	"fmt"
	"strings"
)

// 不使用数据结构和算法，直接用内置的 Replace() 方法将字符串中的 () ， [] ，{} 全部替换成空字符串，替换之后如果字符串的长度为0就说明是一个“有效的括号” 字符串。
// 时间复杂度: O(N^2)，空间复杂度: O(N)
func isValidBrackets1(s string) bool {
	for {
		l := len(s)
		s = strings.Replace(s, "()", "", -1)
		s = strings.Replace(s, "[]", "", -1)
		s = strings.Replace(s, "{}", "", -1)
		//判断s是否没变过，相当于s不存在(),[],{}
		if len(s) == l {
			break
		}
	}
	return len(s) == 0
}

// 用 栈 来实现，利用栈的后进先出的特性，如果是左括号就入栈，如果是右括号则查看当前栈顶元素是否与当前元素匹配，如果不匹配直接返回 false；如果全部匹配成功则返回 true。
// 时间复杂度: O(N)，空间复杂度: O(N)。
func isValidBrackets2(s string) bool {
	if len(s)%2 != 0 { //如果左右括号的个数是奇数则肯定返回false
		return false
	}
	stack := make([]rune, len(s))
	n := 0
	for _, c := range s {
		switch c {
		case '(', '[', '{':
			stack[n] = c
			n++
		case ')':
			if n == 0 || stack[n-1] != '(' {
				return false
			}
			n--
		case ']':
			if n == 0 || stack[n-1] != '[' {
				return false
			}
			n--
		case '}':
			if n == 0 || stack[n-1] != '{' {
				return false
			}
			n--
		}
	}

	if n == 0 {
		return true
	} else {
		return false
	}
}
func main() {
	fmt.Println(isValidBrackets1("[]()")) //true
	fmt.Println(isValidBrackets1("[])"))  //false

	fmt.Println(isValidBrackets2("[]()")) //true
	fmt.Println(isValidBrackets2("[])"))  //false
	fmt.Println(isValidBrackets2("[]))")) //false
}
